#pragma once

#include <vector>
#include <queue>
#include <cstdlib>

#define BITS_IN_BYTE 8
#define COUNT_OF_BYTES_IN_INT 4

using namespace std;

struct edge{
	int parent, son;
	
	edge(int parent, int son){
		this->parent = parent;
		this->son = son;
	}
};

class IDigraph{
public:
	virtual ~IDigraph(){}

	virtual int get_number_of_vertices() const = 0;
	
	virtual vector<int> get_incidence_list(int vertex) const = 0;
	
	virtual int bytesize() const = 0;
};

class Matrix : public IDigraph{
public:
	Matrix(int vertices, const vector<edge> & Edges){
		matrix.resize(vertices);
		for (int i = 0; i < vertices; i++){
			matrix[i].resize(vertices, 0);
		}
		for (int i = 0; i < Edges.size(); i++){
			matrix[Edges[i].parent][Edges[i].son] = true;
		}
	}
	
	int get_number_of_vertices() const
	{
		return matrix.size();
	}
		
	vector<int> get_incidence_list(int vertex) const
	{
		vector<int> result;
		for (int i = 0; i < matrix[vertex].size(); i++){
			if (matrix[vertex][i]) result.push_back(i);
		}
		return result;
	}
	
	int bytesize() const
	{
		int n = get_number_of_vertices();
		return n * n / BITS_IN_BYTE;
	}
private:
	vector<vector<bool> > matrix;
};

class IncidenceLists : public IDigraph{
public:
	IncidenceLists(int vertices, const vector<edge> & Edges){
		lists.resize(vertices, vector<int>(0));
		for (int i = 0; i < Edges.size(); i++){
			lists[Edges[i].parent].push_back(Edges[i].son);
		}
	}
	
	int get_number_of_vertices() const
	{
		return lists.size();
	}
	
	vector<int> get_incidence_list(int vertex) const
	{
		return lists[vertex];
	}
	
	int bytesize() const
	{
		int ans = 0;
		for (int i = 0; i < lists.size(); i++) ans += lists[i].size();
		return ans * COUNT_OF_BYTES_IN_INT;
	}
private:
	vector<vector<int> > lists;
};

IDigraph* make_compact_digraph(int vertices, const vector<edge> & Edges){		//Edges starts with a big letter because it's a set, not a count
	if (vertices * vertices / BITS_IN_BYTE < Edges.size() * COUNT_OF_BYTES_IN_INT)
	return new Matrix(vertices, Edges); else									//according to rules, edges is just #(Edges) = |Edges| = Edges.size()
	return new IncidenceLists(vertices, Edges);
}

template <class func>
void bfs(const IDigraph& digraph, int vertex, func* make = NULL){
	queue<int> q;	//q means queue, it's used only here
	q.push(vertex);
	vector<bool> used(digraph.get_number_of_vertices(), false);
	while (!q.empty()){
		int cur = q.front();
		q.pop();
		if (used[cur]) continue;
		vector<int> neighbours = digraph.get_incidence_list(cur);
		used[cur] = true;
		for (int i = 0; i < neighbours.size(); i++){
			if (!used[neighbours[i]]) q.push(neighbours[i]);
		}
		if (make) *make(cur);
	}
}

template <class func1, class func2>
void dfs(const IDigraph& digraph, int vertex, func1 *before = NULL, func2 *after = NULL){
	vector<int> color(digraph.get_number_of_vertices(), 0);	//0 -- white, 1 -- gray, 2 -- black
	vector<int> stack(1, vertex);
	vector<int> last(color.size(), 0);
	vector<vector<int> > incidences(1, digraph.get_incidence_list(vertex));	//if we want to economy memory instead of time, I can not to keep it
	while (!stack.empty()){
		int cur = stack.back();
		if (last[cur] == incidences[cur].size()){
			stack.pop_back();
			incidences.pop_back();
			color[cur] = 2;
			if (after) (*after)(cur);
		} else {
			int next = incidences.back()[last[cur]++];
			if (color[next] == 0){
				stack.push_back(next);
				incidences.push_back(digraph.get_incidence_list(next));
				color[next] = 1;
				if (before) (*before)(next);
			}
		}
	}
}

class topsorter{
public:
	topsorter(){ result.clear(); used.clear(); };
	
	~topsorter(){};
	
	void operator ()(int x){
		result.push_back(x);
		used[x] = true;
	}
	
	bool was(int vertex){
		return used[vertex];
	}
	
	void resize(int count){
		used.resize(count, false);
	}
	
	vector<int> get_result(){
		return result;
	}
private:
	vector<int> result;
	vector<bool> used;
};

vector<int> topsort(const IDigraph& digraph){
	topsorter for_topsort;
	int vertices = digraph.get_number_of_vertices();
	for_topsort.resize(vertices);
	for (int i = 0; i < vertices; i++){
		if (!for_topsort.was(i)){
			dfs(digraph, i, (topsorter*)NULL, &for_topsort);
		}
	}
	return for_topsort.get_result();
}